package entities;

import graph.Vertex;
import graph.Edge;
import graph.Graph;

import antGraph.AntVertex;
import antGraph.AntEdge;
import antGraph.AntGraph;

import java.util.LinkedHashSet;
import java.util.Random;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

/*
 * authors: Clayson Celes and Andrey Bicalho
 */
public class Ant {

	private Graph graph;

	private Vertex initialVertex;

	private Vertex currentVertex;

	private Random random;

	/** The initial behavior is to search for food */
	private AntBehavior currentBehavior = AntBehavior.SEARCH_FOOD;

	private static final double BACK_PENALTY = .0001;

	static final double ALPHA = 1.0;

	private boolean dropPheromone = false;

	 private CustomStack<Vertex> vertexStack;

	/*
	 * Each ant has two behaviors: search for food and return to the nest 
	 */
	public enum AntBehavior {
		SEARCH_FOOD, RETURN_NEST
	}

	/*
	 * Constructor
	 */
	public Ant(Graph graph, Vertex currentVertex) {
		this(graph, currentVertex, new Random(System.currentTimeMillis()));
	}

	public Ant(Graph graph, Vertex currentVertex, Random random) {
		this.currentVertex = currentVertex;
		this.initialVertex = currentVertex;
		this.graph = graph;
		this.random = random;

		this.vertexStack = new CustomStack<Vertex>();
	}

	public boolean walk(Vertex destinationVertex) {
		if (canWalk(destinationVertex)) {
			if (currentBehavior != AntBehavior.RETURN_NEST) {
				 vertexStack.push(currentVertex); //places the current vertex on the stack
			}
			
			currentVertex = destinationVertex; //update the current vertex

			if (isInitialVertex()) {
				currentBehavior = AntBehavior.SEARCH_FOOD;
				vertexStack = new CustomStack<Vertex>();
			}

			if (hasFoodHere()) {
				currentBehavior = AntBehavior.RETURN_NEST;
				dropPheromone = true;
			}
			return true;
		}
		return false;
	}
	
	/*
	 * Checks if is possible to walk to the destination vertex.
	 * First, gets the edges from current vertex. After that, check that the edge exists.
	 * If edge exists, check that the destination is one of the two nodes. 
	 */	
	private boolean canWalk(Vertex destinationVertex) {
		HashSet<Edge> edges = graph.getEdgesByVertex(currentVertex);
		if (edges == null) {
			return false;
		}

		for (Edge edge : edges) {
			if (edge != null && (edge.getNode1() == destinationVertex || edge.getNode2() == destinationVertex)) {
				return true;
			}
		}
		return false;
	}

	private boolean isInitialVertex() {
		return currentVertex.equals(initialVertex);
	}
	
	private boolean hasFoodHere() {
		if (this.currentVertex instanceof AntVertex) {
			return ((AntVertex) this.currentVertex).hasFood();
		} else {
			return false;
		}
	}

	public AntBehavior getCurrentBehavior() {
		return currentBehavior;
	}

	public Vertex getCurrentVertex() {
		return currentVertex;
	}

	public Vertex chooseNextMove() throws IllegalStateException {
		if (currentBehavior == AntBehavior.SEARCH_FOOD) {
			HashSet<Edge> edges = graph.getEdgesByVertex(currentVertex);

			excretePheromoneIfSeesPheromone(edges);

			if (edges.size() == 0) {//throw the exception
				throw new IllegalStateException("The current vertex has no neighbors");
			}

			double totalCost = 0.0;
			Set<RangedEdge> ranges = new LinkedHashSet<Ant.RangedEdge>();
			for (Edge edge : edges) {
				double cost = edge.getCost();

				// Penalyze backwards movements
				if (!vertexStack.empty()) {
					Vertex previousLocation = vertexStack.peek();
					if (edge.getNode1().equals(previousLocation)
							|| edge.getNode2().equals(previousLocation)) {
						cost = cost * BACK_PENALTY;
					}
				}

				cost = Math.pow(cost, ALPHA);
				ranges.add(new RangedEdge(edge, totalCost, totalCost + cost));
				totalCost += cost;
			}
			// logger.finest(ranges.toString());

			double comparisonValue = random.nextDouble() * totalCost;
			for (RangedEdge range : ranges) {
				if (range.isInRange(comparisonValue)) {
					Edge edge = range.getEdge();
					if (!edge.getNode1().equals(currentVertex)) {
						if (dropPheromone) {
							addPheromone(edge.getNode1(), .1);
						}
						return edge.getNode1();
					} else {
						// logger.fine(String.format("Ant chose %s",
						// edge.getNode2()));
						if (dropPheromone) {
							addPheromone(edge.getNode2(), .01);
						}
						return edge.getNode2();
					}
				}
			}
			throw new IllegalStateException("Didn't find a best edge to follow");
		}
		
		if (currentBehavior == AntBehavior.RETURN_NEST) {
			Vertex nextVertex = vertexStack.pop();
			if (dropPheromone) {
				addPheromone(nextVertex, 1);
			} else {
				throw new IllegalStateException(
						"We're returning and for some reason not dropping pheromone.");
			}
			// FOR EACH edge in the intersection, deposit pheromone
			return nextVertex;
		}

		throw new IllegalStateException("Unknown antBehavior: " + currentBehavior);
	}

	private void excretePheromoneIfSeesPheromone(HashSet<Edge> edges) {
		for (Edge edge : edges) {
			if (edge.getCost() > 1.0) {
				dropPheromone = true;
			}
		}
	}

	private void addPheromone(Vertex nextVertex, double pheromone) {
		HashSet<Edge> edgesCurrentVertex = graph.getEdgesByVertex(currentVertex);
		HashSet<Edge> edgesNextVertex = graph.getEdgesByVertex(nextVertex);
		Set<Edge> edges = Ant.intersection(edgesCurrentVertex, edgesNextVertex);
		for (Edge edge : edges) {
			AntEdge antEdge = (AntEdge) edge;
			antEdge.addPheromone(pheromone);

			// logger.fine(String.format("*****Deposited pheromone at %s",
			// antEdge));
		}
	}
	
	
	/*
	 * Returns the intersection between two Sets
	 */
	public static <T> Set<T> intersection(Set<T> setA, Set<T> setB) {
		Set<T> tmp = new TreeSet<T>();
		for (T x : setA)
			if (setB.contains(x))
				tmp.add(x);
		return tmp;
	}

	class RangedEdge {
		private double start;
		private double end;
		private Edge edge;

		public RangedEdge(Edge edge, double start, double end) {
			this.start = start;
			this.end = end;
			this.edge = edge;
		}

		public double getEnd() {
			return end;
		}

		public double getStart() {
			return start;
		}

		public Edge getEdge() {
			return edge;
		}

		public boolean isInRange(double value) {
			if (value >= start && value < end) {
				return true;
			}
			return false;
		}

		@Override
		public String toString() {
			String myString = "Start: " + start + ", End: " + end + "Edge: " + edge.toString();
			return myString;
		}
	}
	
	class CustomStack<T> extends Stack<T> {

		Set<T> elementSet = new HashSet<T>();

		public T push(T element) {
			if (!elementSet.contains(element)) {
				elementSet.add(element);
			} else {
				while (!this.isEmpty() && this.pop() != element) {
				}
				elementSet = new HashSet<T>();
				elementSet.addAll(this);
			}
			return super.push(element);
		}

	}
}
